{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Redundant Connection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findRedundantConnection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #冗余连接"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>树可以看成是一个连通且 <strong>无环&nbsp;</strong>的&nbsp;<strong>无向&nbsp;</strong>图。</p>\n",
    "\n",
    "<p>给定往一棵&nbsp;<code>n</code> 个节点 (节点值&nbsp;<code>1～n</code>) 的树中添加一条边后的图。添加的边的两个顶点包含在 <code>1</code> 到 <code>n</code>&nbsp;中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 <code>n</code> 的二维数组 <code>edges</code>&nbsp;，<code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;表示图中在 <code>ai</code> 和 <code>bi</code> 之间存在一条边。</p>\n",
    "\n",
    "<p>请找出一条可以删去的边，删除后可使得剩余部分是一个有着 <code>n</code> 个节点的树。如果有多个答案，则返回数组&nbsp;<code>edges</code>&nbsp;中最后出现的那个。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode-cn.com/1626676174-hOEVUL-image.png\" style=\"width: 152px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> edges = [[1,2], [1,3], [2,3]]\n",
    "<strong>输出:</strong> [2,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode-cn.com/1626676179-kGxcmu-image.png\" style=\"width: 250px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]\n",
    "<strong>输出:</strong> [1,4]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == edges.length</code></li>\n",
    "\t<li><code>3 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= ai&nbsp;&lt; bi&nbsp;&lt;= edges.length</code></li>\n",
    "\t<li><code>ai != bi</code></li>\n",
    "\t<li><code>edges</code> 中无重复元素</li>\n",
    "\t<li>给定的图是连通的&nbsp;</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [redundant-connection](https://leetcode.cn/problems/redundant-connection/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [redundant-connection](https://leetcode.cn/problems/redundant-connection/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[1,3],[2,3]]', '[[1,2],[2,3],[3,4],[1,4],[1,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)+1\n",
    "        father = [0]*n\n",
    "        for i in range(n):\n",
    "            father[i] = i\n",
    "        def find(a):\n",
    "            if a==father[a]:\n",
    "                return a\n",
    "            father[a] = find(father[a])\n",
    "            return father[a]\n",
    "        def same(a,b):\n",
    "            a = find(a)\n",
    "            b = find(b)\n",
    "            return a==b\n",
    "        def join(a,b):\n",
    "            a = find(a)\n",
    "            b = find(b)\n",
    "            if a==b:\n",
    "                return\n",
    "            father[b] = a\n",
    "        for e in edges:\n",
    "            if not same(e[0],e[1]):\n",
    "                join(e[0],e[1])\n",
    "            else:\n",
    "                return e\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        p = list(range(len(edges)+1))\n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        def join(a, b):\n",
    "            a = find(a)\n",
    "            b = find(b)\n",
    "            if a == b:\n",
    "                return \n",
    "            p[b] = a\n",
    "        for a, b in edges:\n",
    "            if find(a) == find(b):\n",
    "                return [a, b]\n",
    "            join(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)+1\n",
    "        father = [0]*n\n",
    "        for i in range(n):\n",
    "            father[i] = i\n",
    "        def find(a):\n",
    "            if a==father[a]:\n",
    "                return a\n",
    "            father[a] = find(father[a])\n",
    "            return father[a]\n",
    "        def same(a,b):\n",
    "            a = find(a)\n",
    "            b = find(b)\n",
    "            return a==b\n",
    "        def join(a,b):\n",
    "            a = find(a)\n",
    "            b = find(b)\n",
    "            if a==b:\n",
    "                return\n",
    "            father[b] = a\n",
    "        for e in edges:\n",
    "            if not same(e[0],e[1]):\n",
    "                join(e[0],e[1])\n",
    "            else:\n",
    "                return e\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        UF = UnionFind(n)\n",
    "        for u, v in edges:\n",
    "            if UF.isSameSet(u-1, v-1):\n",
    "                return [u, v]\n",
    "            else:\n",
    "                UF.unionSet(u-1, v-1)\n",
    "\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int, m: int=None) -> None:\n",
    "        \"\"\"\n",
    "        build m disjoint sets from n nodes\n",
    "        T: O(N)\n",
    "        \"\"\"\n",
    "        self.parents = list(range(n))    \n",
    "        self.ranks = [0] * n            \n",
    "    \n",
    "    def findSet(self, i: int) -> int:\n",
    "        \"\"\"return root of node i's set\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "           path-compression  \n",
    "           Recursion\n",
    "        \"\"\"\n",
    "        if self.parents[i] == i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parents[i] = self.findSet(self.parents[i])\n",
    "            return self.parents[i]\n",
    "        \n",
    "    \n",
    "    def unionSet(self, i: int, j: int) -> None:\n",
    "        \"\"\"若节点i和节点j来自2个不同的互斥集合，将两个集合合并 \n",
    "           union by rank   矮树作为高树的子树\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        ip, jp = self.findSet(i), self.findSet(j)\n",
    "\n",
    "        # 若两个节点来自同一互斥集合，返回\n",
    "        if ip == jp:\n",
    "            return \n",
    "\n",
    "        # 若A树矮，B树高，A树连到B树的根节点上，新树rank不变\n",
    "        if self.ranks[ip] < self.ranks[jp]:\n",
    "            self.parents[ip] = jp\n",
    "\n",
    "        # 若B树矮，A树高，B树连到A树的根节点上，新树rank不变\n",
    "        elif self.ranks[jp] < self.ranks[ip]:\n",
    "            self.parents[jp] = ip\n",
    "\n",
    "        # 若两树等高，任选一种方案，新树 rank +1\n",
    "        else:\n",
    "            self.parents[jp] = ip\n",
    "            self.ranks[ip] += 1\n",
    "\n",
    "    \n",
    "    def isSameSet(self, i: int, j: int) -> bool:\n",
    "        \"\"\"判断节点i和节点j是否属于同一集合\n",
    "           T: O(α(N) first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        # path compression twice\n",
    "        return self.findSet(i) == self.findSet(j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        graph = collections.defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "\n",
    "        visit = []\n",
    "        res = []\n",
    "        indicator = False\n",
    "        @functools.cache\n",
    "        def dfs(u,pre):\n",
    "            nonlocal visit, res,indicator\n",
    "            visit.append(u)\n",
    "            for v in graph[u]:\n",
    "                if v != pre:\n",
    "                    if v in visit:\n",
    "                        ind = visit.index(v)\n",
    "                        res= visit[ind:] + [v]\n",
    "                        indicator = True\n",
    "                        return\n",
    "                    else:\n",
    "                        dfs(v,u)\n",
    "                        if indicator == True:\n",
    "                            return\n",
    "                        visit.pop()\n",
    "        dfs(1,-1)\n",
    "        result = []\n",
    "        k = len(res)\n",
    "        for i in range(k-1):\n",
    "            result.append([res[i],res[i+1]])\n",
    "        edges =edges[::-1]    \n",
    "        for a,b in edges:\n",
    "            if [a,b] in result or [b,a] in result:\n",
    "                return [a,b]\n",
    "            \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.n = 1001\n",
    "        self.father = [i for i in range(self.n)]\n",
    "    \n",
    "    def find(self, i):\n",
    "        if self.father[i] != i:\n",
    "            self.father[i] = self.find(self.father[i])\n",
    "        return self.father[i]\n",
    "    \n",
    "    def join(self, u, v):\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        if u != v:\n",
    "            self.father[v] = u\n",
    "    \n",
    "    def is_same(self, u, v):\n",
    "        return self.find(u) == self.find(v)\n",
    "\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        for u, v in edges:\n",
    "            if self.is_same(u-1, v-1):\n",
    "                return [u, v]\n",
    "            else:\n",
    "                self.join(u-1, v-1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        self.father = list(range(len(edges)+1))\n",
    "        for e in edges:\n",
    "            if self.isSame(e[0], e[1]):\n",
    "                return e\n",
    "            else:\n",
    "                self.join(e[0], e[1])\n",
    "        return []\n",
    "\n",
    "\n",
    "    def find(self, u):\n",
    "        if u != self.father[u]:\n",
    "            self.father[u] = self.find(self.father[u])\n",
    "        return self.father[u]\n",
    "    \n",
    "    def join(self, u, v):\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        if u == v:\n",
    "            return \n",
    "        self.father[u] = v\n",
    "    \n",
    "    def isSame(self, u, v):\n",
    "        if self.find(u) == self.find(v):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, size):\n",
    "        self.parent = [0] * size\n",
    "        for i in range(size):\n",
    "            self.parent[i] = i\n",
    "    \n",
    "    def find(self, index):\n",
    "        if index != self.parent[index]:                             # keep finding until hit parent\n",
    "            self.parent[index] = self.find(self.parent[index])\n",
    "        \n",
    "        return self.parent[index]\n",
    "\n",
    "    def union(self, index1, index2):                                # merge parent\n",
    "        self.parent[self.find(index2)] = self.find(index1)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        n = len(edges) + 1\n",
    "        uf = UnionFind(n)\n",
    "\n",
    "        for (x, y) in edges:\n",
    "            if uf.find(x) != uf.find(y):\n",
    "                uf.union(x, y)\n",
    "            else:                             # find last one\n",
    "                return (x, y)\n",
    "        \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        p = [i for i in range(n+1)]\n",
    "        def find(i):\n",
    "            if p[i] != i:\n",
    "                p[i] = find(p[i])\n",
    "            return p[i]\n",
    "        for u,v in edges:\n",
    "            if find(u) == find(v):\n",
    "                return [u,v]\n",
    "            p[find(u)] = find(v)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindSet:\n",
    "    def __init__(self,n):\n",
    "        self._parents = [i for i in range(n+1)]\n",
    "        self._rank = [0 for i in range(n+1)]\n",
    "    \n",
    "    def find(self,x):\n",
    "        while x!=self._parents[x]:\n",
    "            self._parents[x]=self._parents[self._parents[x]]\n",
    "            x = self._parents[x]\n",
    "        return x\n",
    "    \n",
    "    def union(self,x,y):\n",
    "        px,py = self.find(x),self.find(y)\n",
    "        if px == py : return False\n",
    "\n",
    "        if self._rank[px]>self._rank[py]:\n",
    "            self._parents[py]=px\n",
    "        if self._rank[py]>self._rank[px]:\n",
    "            self._parents[px]=py\n",
    "        if self._rank[px]==self._rank[py]:\n",
    "            self._parents[py]=px\n",
    "            self._rank[px]+=1\n",
    "\n",
    "        return True\n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        s=UnionFindSet(len(edges))\n",
    "        for edge in edges:\n",
    "            if not s.union(edge[0],edge[1]):return edge"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n+1))\n",
    "        def find(index):\n",
    "            if parent[index] != index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "        \n",
    "        def union(ind1, ind2):\n",
    "            parent[find(ind1)] = find(ind2)\n",
    "        \n",
    "        for n1, n2 in edges:\n",
    "            if find(n1) != find(n2):\n",
    "                union(n1, n2)\n",
    "            else:\n",
    "                return [n1,n2]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findRedundantConnection(self, edges):\n",
    "        n = len(edges)\n",
    "        father = [i for i in range(n)]\n",
    "        def find(i):\n",
    "            if i != father[i]:\n",
    "                father[i] = find(father[i])\n",
    "            return father[i]\n",
    "        for u, v in edges:\n",
    "            if find(u-1) == find(v-1):\n",
    "                return [u, v]\n",
    "            else:\n",
    "                father[find(u-1)] = find(v-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n+1))\n",
    "\n",
    "        def find(index):\n",
    "            if parent[index] != index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "        \n",
    "        def union(index1, index2):\n",
    "            parent[find(index1)] = find(index2)\n",
    "\n",
    "        for node1, node2 in edges:\n",
    "            if find(node1) != find(node2):\n",
    "                union(node1, node2)\n",
    "            else:\n",
    "                return [node1, node2]\n",
    "        \n",
    "        # return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n+1))\n",
    "\n",
    "        def find(index):\n",
    "            if parent[index] != index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "        \n",
    "        def union(index1, index2):\n",
    "            parent[find(index1)] = find(index2)\n",
    "\n",
    "        for node1, node2 in edges:\n",
    "            if find(node1) != find(node2):\n",
    "                union(node1, node2)\n",
    "            else:\n",
    "                return [node1, node2]\n",
    "        \n",
    "        # return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n+1))\n",
    "        def find(index):\n",
    "            if parent[index] != index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "        def union(index1, index2):\n",
    "            parent[find(index1)] = find(index2)\n",
    "        for node1, node2 in edges:\n",
    "            if find(node1) != find(node2):\n",
    "                union(node1, node2)\n",
    "            else:\n",
    "                res = [node1, node2]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        # 每一次加入一条边都是join\n",
    "        # 冗余边意味着边两端的元素已经在同一个集合内了\n",
    "        # 且由于题目中节点为n，边为n，所以必然只有一条\n",
    "        n=len(edges)\n",
    "        father=[i for i in range(n+5)]\n",
    "\n",
    "        def find(u):\n",
    "            nonlocal father\n",
    "            if u==father[u]:\n",
    "                return u\n",
    "            else:\n",
    "                father[u]=find(father[u])\n",
    "                return father[u]\n",
    "        \n",
    "        def join(u,v):\n",
    "            nonlocal father\n",
    "            pu=find(u)\n",
    "            pv=find(v)\n",
    "            if pu==pv:\n",
    "                return\n",
    "            father[pv]=pu\n",
    "        \n",
    "        def isSame(u,v):\n",
    "            nonlocal father\n",
    "            pu=find(u)\n",
    "            pv=find(v)\n",
    "            return pu==pv\n",
    "        \n",
    "        for edge in edges:\n",
    "            if not isSame(edge[0],edge[1]):\n",
    "                join(edge[0],edge[1])\n",
    "            else:\n",
    "                return edge\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "\n",
    "        p = [i for i in range(n + 1)]\n",
    "\n",
    "        def find(i):\n",
    "            if p[i] != i:\n",
    "                p[i] = find(p[i])\n",
    "            return p[i]\n",
    "\n",
    "        for u, v in edges:\n",
    "            if find(u) == find(v):\n",
    "                return [u, v]\n",
    "            else:\n",
    "                p[find(u)] = find(v)\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n + 1))\n",
    "        def find(index: int) -> int:\n",
    "            if parent[index] != index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "\n",
    "        def union(index1: int, index2: int):\n",
    "            parent[find(index1)] = find(index2)\n",
    "\n",
    "        for node1, node2 in edges:\n",
    "            if find(node1) != find(node2):\n",
    "                union(node1, node2)\n",
    "            else:\n",
    "                return [node1, node2]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, M):\n",
    "        self.parent = {}\n",
    "        self.cnt = 0\n",
    "        # 初始化 parent，size 和 cnt\n",
    "        for i in range(M):\n",
    "            self.parent[i] = i\n",
    "            self.cnt += 1\n",
    "\n",
    "    def find(self, x):\n",
    "        if x != self.parent[x]:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "            return self.parent[x]\n",
    "        return x\n",
    "    def union(self, p, q):\n",
    "        if self.connected(p, q): return\n",
    "        leader_p = self.find(p)\n",
    "        leader_q = self.find(q)\n",
    "        self.parent[leader_p] = leader_q\n",
    "        self.cnt -= 1\n",
    "    def connected(self, p, q):\n",
    "        return self.find(p) == self.find(q)\n",
    "        \n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        uf = UF(1001)\n",
    "        for fr, to in edges:\n",
    "            if uf.connected(fr, to): return [fr, to]\n",
    "            uf.union(fr, to)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n=len(edges)\n",
    "        parent=list(range(n+1))\n",
    "\n",
    "        def find(index):\n",
    "            if parent[index]!=index:\n",
    "                parent[index]=find(parent[index])\n",
    "            return parent[index]\n",
    "        \n",
    "        def union(index,index2):\n",
    "            parent[find(index)]=find(index2)\n",
    "\n",
    "        for node1,node2 in edges:\n",
    "            if find(node1)!=find(node2):\n",
    "                union(node1,node2)\n",
    "            else:\n",
    "                return [node1,node2]\n",
    "        return []\n",
    "            \n",
    "        return []\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n + 1))\n",
    "\n",
    "        def find(index):\n",
    "            if parent[index] != index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "        \n",
    "        def union(index1, index2):\n",
    "            parent[find(index1)] = find(index2)\n",
    "\n",
    "        for node1, node2 in edges:\n",
    "            if find(node1) != find(node2):\n",
    "                union(node1, node2)\n",
    "            else:\n",
    "                return [node1, node2]\n",
    "        \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n + 1))\n",
    "\n",
    "        def find(index: int) -> int:\n",
    "            if parent[index] != index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "        \n",
    "        def union(index1: int, index2: int):\n",
    "            parent[find(index1)] = find(index2)\n",
    "\n",
    "        for node1, node2 in edges:\n",
    "            if find(node1) != find(node2):\n",
    "                union(node1, node2)\n",
    "            else:\n",
    "                return [node1, node2]\n",
    "        \n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        father = [i for i in range(n+1)]\n",
    "        \n",
    "        def find(node):\n",
    "            if father[node] != node:\n",
    "                father[node] = find(father[node])\n",
    "            return father[node]\n",
    "        \n",
    "        for i,v in edges:\n",
    "            if find(i) == find(v):\n",
    "                return [i,v]\n",
    "            # 将节点 i 的根节点更新为节点 v 的根节点\n",
    "            father[father[i]] = find(v) # 这样是错误的father[i] = find(v)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n=len(edges)\n",
    "        fa=[i for i in range(n+1)]\n",
    "        def find(x):\n",
    "            if fa[x]!=x:\n",
    "                fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        for i,j in edges:\n",
    "            x=find(i)\n",
    "            y=find(j)\n",
    "            if x!=y:\n",
    "                fa[x]=y\n",
    "            else:\n",
    "                return [i,j]\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        p = [i for i in range(n+1)]\n",
    "        def find(i):\n",
    "            if p[i] != i:\n",
    "                p[i] = find(p[i])\n",
    "            return p[i]\n",
    "        for u, v in edges:\n",
    "            if p[find(u)] == find(v):\n",
    "                return [u, v]\n",
    "            p[find(u)] = find(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        l_e = len(edges)\n",
    "        # print(edges)\n",
    "        cur = l_e - 1\n",
    "        n = max([_[1] for _ in edges])\n",
    "\n",
    "        def find(x, uf):\n",
    "            while uf[x] != x:\n",
    "                uf[x] = uf[uf[x]]\n",
    "                x = uf[x]\n",
    "            return x\n",
    "\n",
    "        def union(x, y, uf):\n",
    "            rootx = find(x, uf)\n",
    "            rooty = find(y, uf)\n",
    "            if rootx != rooty:\n",
    "                uf[rootx] = rooty\n",
    "\n",
    "        while cur >= 0:\n",
    "            tmp_lst = edges[:cur] + edges[cur + 1:]\n",
    "            tmp_uf = {i: i for i in range(1, n + 1)}\n",
    "            # print(tmp_lst)\n",
    "            for tmp in tmp_lst:\n",
    "                union(tmp[0], tmp[1], tmp_uf)\n",
    "                # print(tmp_uf)\n",
    "            for k in tmp_uf:\n",
    "                tmp_uf[k] = find(k, tmp_uf)\n",
    "            # print(tmp_uf)\n",
    "            if len(set(tmp_uf.values())) == 1:\n",
    "                return edges[cur]\n",
    "            cur -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [0] * (n + 1)\n",
    "\n",
    "        for i in range(n):\n",
    "            self.parent[i] = i\n",
    "    \n",
    "    def find(self, idx):\n",
    "\n",
    "        while self.parent[idx] != idx:\n",
    "            idx = self.parent[idx]\n",
    "        return idx\n",
    "\n",
    "    def union(self, idx1, idx2):\n",
    "        root1 = self.find(idx1)\n",
    "        root2 = self.find(idx2)\n",
    "\n",
    "        if root1 == root2:\n",
    "            return\n",
    "        \n",
    "        self.parent[root1] = root2\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        n = len(edges)\n",
    "        uf = UnionFind(n + 1)\n",
    "\n",
    "        for (x, y) in edges:\n",
    "            if uf.find(x) != uf.find(y):\n",
    "                uf.union(x, y)\n",
    "            \n",
    "            else:\n",
    "                return[x, y]\n",
    "        \n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        pre = [i for i in range(len(edges) + 1)]\n",
    "        def find(x):\n",
    "            if pre[x] == x:\n",
    "                return pre[x]\n",
    "            else:\n",
    "                pre[x] = find(pre[x])\n",
    "                return pre[x]\n",
    "        def join(x, y):\n",
    "            bx = find(x)\n",
    "            by = find(y)\n",
    "            if bx != by:\n",
    "                pre[by] = bx\n",
    "        \n",
    "        for eg in edges:\n",
    "            left = find(eg[0])\n",
    "            right = find(eg[1])\n",
    "            if left == right:\n",
    "                return eg\n",
    "            else:\n",
    "                join(left, right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n + 1))\n",
    "\n",
    "        def union(x, y):\n",
    "            rootX = find(x)\n",
    "            rootY = find(y)\n",
    "            parent[rootX] = rootY\n",
    "\n",
    "        def find(x):\n",
    "            origin = parent[x]\n",
    "            if origin != parent[origin]:\n",
    "                parent[x] = find(origin)\n",
    "            return parent[x]\n",
    "        \n",
    "        for x, y in edges:\n",
    "            if find(x) != find(y):\n",
    "                union(x, y)\n",
    "            else:\n",
    "                return [x, y]\n",
    "        \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        # 初始化\n",
    "        n = len(edges)\n",
    "        mapping = [i for i in range(n+1)]\n",
    "\n",
    "        def find(node):\n",
    "            if mapping[node] == node:\n",
    "                return node\n",
    "            else:\n",
    "                # 不断的往上找祖先\n",
    "                mapping[node] = find(mapping[node])\n",
    "                return mapping[node]\n",
    "\n",
    "\n",
    "        for edge in edges:\n",
    "            root1 = find(edge[0])\n",
    "            root2 = find(edge[1])\n",
    "            print\n",
    "            if root1 == root2:\n",
    "                return edge\n",
    "            else:\n",
    "                mapping[root1] = root2\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        par=[i for i in range(len(edges)+1)]\n",
    "        rank=[1]*(len(edges)+1)\n",
    "        def find(n):\n",
    "            p=par[n]\n",
    "            while p !=par[p]:\n",
    "                par[p]=par[par[p]]\n",
    "                p=par[p]\n",
    "            return p\n",
    "        def union(n1,n2):\n",
    "            p1,p2=find(n1),find(n2)\n",
    "            if p1==p2:\n",
    "                return False\n",
    "            if rank [p1]>rank[p2]:\n",
    "                par[p2]=p1\n",
    "                rank[p1]+=rank[p2]\n",
    "            else:\n",
    "                par[p1]=p2\n",
    "                rank[p2]+=rank[p1]\n",
    "            return True\n",
    "        for n1,n2 in edges:\n",
    "            if not union(n1,n2):\n",
    "                return[n1,n2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        parent = list(range(len(edges) + 1))\n",
    "\n",
    "        def find_node(node: int) -> int:\n",
    "            if parent[node] != node:\n",
    "                parent[node] = find_node(parent[node])\n",
    "            return parent[node]\n",
    "\n",
    "        def union_nodes(node1: int, node2: int):\n",
    "            parent[find_node(node1)] = find_node(node2)\n",
    "\n",
    "        for node1, node2 in edges:\n",
    "            if find_node(node1) != find_node(node2):\n",
    "                union_nodes(node1, node2)\n",
    "            else:\n",
    "                return [node1, node2]\n",
    "\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        self.father = [i for i in range(len(edges)+1)]\n",
    "        for edge in edges:\n",
    "            if self.isSame(*edge):\n",
    "                return edge\n",
    "            self.join(*edge)\n",
    "    \n",
    "\n",
    "    def find(self,u):\n",
    "        if self.father[u] == u:\n",
    "            return u\n",
    "        else:\n",
    "            self.father[u] = self.find(self.father[u])\n",
    "            return self.father[u]\n",
    "\n",
    "    def isSame(self,u,v):\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        return u == v\n",
    "    \n",
    "    def join(self,u,v):\n",
    "        nu = self.find(u)\n",
    "        nv = self.find(v)\n",
    "        if nu == nv:\n",
    "            return\n",
    "        self.father[nv] = nu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        father = [i for i in range(n+1)]\n",
    "        \n",
    "        def find(node):\n",
    "            if father[node] != node:\n",
    "                return find(father[node])\n",
    "            return node\n",
    "        \n",
    "        for i,v in edges:\n",
    "            if find(i) == find(v):\n",
    "                return [i,v]\n",
    "\n",
    "            father[find(i)] = find(v)\n",
    "        # n = len(edges)\n",
    "        # father = [i for i in range(n+1)]\n",
    "        \n",
    "        # # def find(node):\n",
    "        # #     if father[node] != node:\n",
    "        # #         # 路径压缩：将node到根节点上的所有节点都连到根节点上\n",
    "        # #         father[node] = find(father[node])\n",
    "        # #     return father[node]\n",
    "        # def find(node):\n",
    "        #     if father[node] != node:\n",
    "        #         return find(father[node])\n",
    "        #     return node\n",
    "        \n",
    "        # for i,v in edges:\n",
    "        #     if find(i) == find(v):\n",
    "        #         return [i,v]\n",
    "        #     # 将节点 i 的根节点更新为节点 v 的根节点\n",
    "        #     father[father[i]] = find(v) # 错误做法：father[i] = find(v)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        parent = list(range(len(edges) + 1))\n",
    "\n",
    "        def find_node(node:int) -> int:\n",
    "            if parent[node] != node:\n",
    "                parent[node] = find_node(parent[node])\n",
    "            return parent[node]\n",
    "\n",
    "        def union_nodes(node1:int, node2:int):\n",
    "            parent[find_node(node1)] = find_node(node2)\n",
    "\n",
    "        for node1, node2 in edges:\n",
    "            if find_node(node1) != find_node(node2):\n",
    "                union_nodes(node1, node2)\n",
    "            else:\n",
    "                return [node1, node2]\n",
    "\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        par = [i for i in range(n+1)]\n",
    "        rank = [1] * (n+1)\n",
    "\n",
    "        def find(n):\n",
    "            p = par[n]\n",
    "\n",
    "            while p != par[p]:\n",
    "                par[p] = par[par[p]]\n",
    "                p = par[p]\n",
    "\n",
    "            return p \n",
    "    \n",
    "        def union(n1, n2):\n",
    "            p1, p2 = find(n1), find(n2)\n",
    "            if p1 == p2:\n",
    "                return False\n",
    "\n",
    "            if rank[p1] >= rank[p2]:\n",
    "                rank[p1] += rank[p2]\n",
    "                par[p2] = p1\n",
    "\n",
    "            else:\n",
    "                rank[p2] += rank[p1]\n",
    "                par[p1] = p2\n",
    "            \n",
    "            return True\n",
    "\n",
    "        for n1, n2 in edges:\n",
    "            if not union(n1, n2):\n",
    "                return [n1, n2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Dsu():\n",
    "    def __init__(self, n):\n",
    "        self.pa = [i for i in range(n)]\n",
    "    def find(self, x):\n",
    "        if self.pa[x] == x:\n",
    "            return x\n",
    "        return self.find(self.pa[x])\n",
    "    def union(self, x, y):\n",
    "        xp = self.find(x)\n",
    "        yp = self.find(y)\n",
    "        self.pa[xp] = self.pa[yp]\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        dsu = Dsu(1007)\n",
    "        res = []\n",
    "        for edge in edges:\n",
    "            from_pt, to_pt = edge\n",
    "            from_pt_pa = dsu.find(from_pt)\n",
    "            to_pt_pa = dsu.find(to_pt)\n",
    "\n",
    "            if from_pt_pa == to_pt_pa:\n",
    "                res = [from_pt, to_pt]\n",
    "            dsu.union(from_pt, to_pt)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = [i for i in range(n)]\n",
    "    \n",
    "    def find(self, n: int) -> int:\n",
    "        while n != self.parent[n]:\n",
    "            c = self.parent[n]\n",
    "            self.parent[n] = self.parent[self.parent[n]]\n",
    "            n = c\n",
    "        return n\n",
    "    \n",
    "    def union(self, i: int, j: int):\n",
    "        px = self.find(i)\n",
    "        py = self.find(j)\n",
    "        if px == py:\n",
    "            return\n",
    "        self.parent[px] = py\n",
    "\n",
    "    def connected(self, i: int, j: int) -> bool:\n",
    "        return self.find(i) == self.find(j)\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        uf = UF(len(edges))\n",
    "        for [x, y] in edges:\n",
    "            if uf.connected(x - 1, y - 1):\n",
    "                return [x, y]\n",
    "            uf.union(x - 1, y - 1)\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        def find(u):\n",
    "            if u == res[u]:\n",
    "                return u\n",
    "            res[u] = find(res[u])\n",
    "            return res[u]\n",
    "\n",
    "        n = len(edges)\n",
    "        res = [i for i in range(n+1)]\n",
    "        for x in edges:\n",
    "            u = find(x[0])\n",
    "            v = find(x[1])\n",
    "            if u == v:\n",
    "                return x\n",
    "\n",
    "            res[v] = u\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        def init(n):\n",
    "            self.f = [i for i in range(n + 1)]\n",
    "            self.rank = [1] * (n + 1)\n",
    "\n",
    "        def find(u):\n",
    "            if u == self.f[u]:\n",
    "                return u\n",
    "            self.f[u] = find(self.f[u])\n",
    "            return self.f[u]\n",
    "\n",
    "        def join(u, v):\n",
    "            u, v = find(u), find(v)\n",
    "\n",
    "            if self.rank[u] < self.rank[v]:\n",
    "                self.f[u] = v\n",
    "            else:\n",
    "                self.f[v] = u\n",
    "                if self.rank[u] == self.rank[v]:\n",
    "                    self.rank[u] += 1\n",
    "\n",
    "        def same(u, v):\n",
    "            u, v = find(u), find(v)\n",
    "            return u == v\n",
    "\n",
    "        n = len(edges)\n",
    "        init(n)\n",
    "        for [u, v] in edges:\n",
    "            if same(u, v):\n",
    "                return [u, v]\n",
    "            else:\n",
    "                join(u, v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        par = [i for i in range(len(edges) + 1)]\n",
    "        n = len(edges)\n",
    "        rank = [1] * (n + 1)\n",
    "\n",
    "        def find(n):\n",
    "            p = par[n]\n",
    "\n",
    "            while p != par[p]:\n",
    "                par[p] = par[par[p]]\n",
    "                p = par[p]\n",
    "\n",
    "            return p\n",
    "\n",
    "        # return False if cannot complete\n",
    "        def union(n1, n2):\n",
    "            p1, p2 = find(n1), find(n2)\n",
    "            if p1 == p2:\n",
    "                return False\n",
    "\n",
    "            if rank[p1] > rank[p2]:\n",
    "                rank[p1] += rank[p2]\n",
    "                par[p2] = p1\n",
    "            else:\n",
    "                rank[p2] += rank[p1]\n",
    "                par[p1] = p2\n",
    "            return True\n",
    "\n",
    "        for n1, n2 in edges:\n",
    "            if not union(n1, n2):\n",
    "                return [n1, n2]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.father = {}\n",
    "    \n",
    "    def add(self, node):\n",
    "        if node not in self.father:\n",
    "            self.father[node] = None\n",
    "    \n",
    "    def find(self, node):\n",
    "        root = node\n",
    "        while self.father[root] != None:\n",
    "            root = self.father[root]\n",
    "        \n",
    "        while node != root:\n",
    "            original_father = self.father[node]\n",
    "            self.father[node] = root\n",
    "            node = original_father\n",
    "        \n",
    "        return root\n",
    "    \n",
    "    def merge(self, node1, node2):\n",
    "        root1, root2 = self.find(node1), self.find(node2)\n",
    "        if root1 == root2:\n",
    "            return False\n",
    "        if root1 != root2:\n",
    "            self.father[root1] = root2\n",
    "            return True\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        uf = UnionFind()\n",
    "        for i in range(1, len(edges) + 1):\n",
    "            uf.add(i)\n",
    "        \n",
    "        for node1, node2 in edges:\n",
    "            if not uf.merge(node1, node2):\n",
    "                return [node1, node2]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, M):\n",
    "        self.parent = {}\n",
    "        self.size = {}\n",
    "        self.cnt = 0\n",
    "        # 初始化 parent，size 和 cnt\n",
    "        # size 是一个哈希表，记录每一个联通域的大小，其中 key 是联通域的根，value 是联通域的大小\n",
    "        # cnt 是整数，表示一共有多少个联通域\n",
    "        for i in range(M):\n",
    "            self.parent[i] = i\n",
    "            self.cnt += 1\n",
    "            self.size[i] = 1\n",
    "\n",
    "    def find(self, x):\n",
    "        if x != self.parent[x]:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "            return self.parent[x]\n",
    "        return x\n",
    "    def union(self, p, q):\n",
    "        if self.connected(p, q): return\n",
    "        # 小的树挂到大的树上， 使树尽量平衡\n",
    "        leader_p = self.find(p)\n",
    "        leader_q = self.find(q)\n",
    "        if self.size[leader_p] < self.size[leader_q]:\n",
    "            self.parent[leader_p] = leader_q\n",
    "            self.size[leader_q] += self.size[leader_p]\n",
    "        else:\n",
    "            self.parent[leader_q] = leader_p\n",
    "            self.size[leader_p] += self.size[leader_q]\n",
    "        self.cnt -= 1\n",
    "    def connected(self, p, q):\n",
    "        return self.find(p) == self.find(q)\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        uf = UF(1001)\n",
    "        for fr, to in edges:\n",
    "            if uf.connected(fr, to): return [fr, to]\n",
    "            uf.union(fr, to)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DisjointSet:\n",
    "    def __init__(self, n):\n",
    "        self.height = dict()\n",
    "        self.parent = dict()\n",
    "        for x in [_ for _ in range(n)]:\n",
    "            self.height[x] = 0\n",
    "            self.parent[x] = x\n",
    "    def find(self, x):\n",
    "        while (x != self.parent[x]):\n",
    "            x = self.parent[x]    \n",
    "        return x\n",
    "    def unionByHeight(self, x, y):\n",
    "        a = self.find(x)\n",
    "        b = self.find(y)\n",
    "\n",
    "        if (self.height[a] <= self.height[b]):\n",
    "            if (self.height[a] == self.height[b]):\n",
    "                self.height[b] += 1\n",
    "            self.parent[a] = b\n",
    "        else:\n",
    "            self.parent[b] = a\n",
    "    def unionByPath(self, x, y):\n",
    "        a = self.find(x)\n",
    "        b = self.find(y)\n",
    "\n",
    "        self.parent[a] = b\n",
    "    def printInfo(self):\n",
    "        print(self.height)\n",
    "        print(self.parent)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        ds = DisjointSet(n)\n",
    "        \n",
    "        res = []\n",
    "        for [x, y] in edges:\n",
    "            a = ds.find(x-1)\n",
    "            b = ds.find(y-1)\n",
    "\n",
    "            if (a == b):\n",
    "                res.append([x,y])\n",
    "            else:\n",
    "                ds.unionByHeight(x-1, y-1)\n",
    "\n",
    "        \n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        fa = list(range(n))\n",
    "\n",
    "        def find(x):\n",
    "            if x!= fa[x]:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        def union(x, y):\n",
    "            fa[find(x)] = find(y)\n",
    "        \n",
    "        for edge in edges:\n",
    "            print(fa)\n",
    "            u, v = edge[0]-1, edge[1]-1\n",
    "            if find(u) != find(v):\n",
    "                union(u, v)\n",
    "            else:\n",
    "                return edge"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        s = [{_} for _ in range(1,n+1)]\n",
    "        def find(i):\n",
    "            for j in range(len(s)):\n",
    "                if i in s[j]:\n",
    "                    return j\n",
    "        for i in edges:\n",
    "            a = find(i[0])\n",
    "            b = find(i[1])\n",
    "            if a != b:\n",
    "                for m in s[b]:\n",
    "                    s[a].add(m)\n",
    "                s.pop(b)\n",
    "            else:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 树就是n个点n-1条边；只要我们遍历时发现有环，那就是我们可以删去的边。\n",
    "    #　因为只有一条冗余连接，所以只形成一个环，那么遍历时就能得到。\n",
    "    # 所以问题转化成：找到图中唯一的一个环并记录。\n",
    "    # 方法1：通过dfs遍历并维护一个state（可用hashset），遇到老朋友的时候就抓住环路即可。\n",
    "    # 缺点是可能递归爆栈。\n",
    "    # 方法2：bfs迭代遍历，每一个dfs节点上维护一个上家，并储存(prev, this)（建立一个新图），并同样维护一个state。当老朋友找到时，通过从新图回溯到老朋友到来获得。\n",
    "    # 缺点是有点麻烦。\n",
    "    # 方法3：通过迭代实现dfs。还不错\n",
    "    # 最后说实话 感觉还是直接dfs，不怕爆栈\n",
    "\n",
    "    # 让我们直接dfs。\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        # 首先把【边表】 变成【邻接表】。\n",
    "        self.n = len(edges)\n",
    "        self.adj = [[] for _ in range(self.n)]\n",
    "        self.been = [False] * self.n # 表示在不在\n",
    "        \n",
    "        \n",
    "        for i in range(self.n):\n",
    "            edge = edges[i]\n",
    "            self.adj[edge[0] - 1].append((edge[1] - 1, i)) # 邻接表中也保存边的序号\n",
    "            self.adj[edge[1] - 1].append((edge[0] - 1, i))\n",
    "        # iterative dfs\n",
    "\n",
    "        self.state = [(0, -1)] # 第一个点不带边号\n",
    "        self.been[0] = True\n",
    "        # print(\"Root: in 0\")\n",
    "        for edge in self.adj[0]:\n",
    "            subres = self.dfs(edge, 0)\n",
    "            if subres >= 0:\n",
    "                # print(\"Root: abort out 0\")\n",
    "                return edges[subres]\n",
    "        # print(\"Root: out 0\")\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "    def dfs(self, tup, prev): # node是节点，idx是边的序号\n",
    "        node, idx = tup\n",
    "        # print(f\"dfs node {node} with edge idx {idx}\")\n",
    "        if self.been[node]: # 如果成环\n",
    "            maxidx = idx\n",
    "            start = -1\n",
    "            for i in range(len(self.state)):\n",
    "                if self.state[i][0] == node: # 找到起始idx\n",
    "                    start = i\n",
    "                    break\n",
    "            for i in range(start + 1, len(self.state)): # 找到最大的idx\n",
    "                curidx = self.state[i][1]\n",
    "                if curidx > maxidx:\n",
    "                    maxidx = curidx\n",
    "            return maxidx\n",
    "\n",
    "        self.state.append((node, idx))\n",
    "        self.been[node] = True\n",
    "        # print(f\"in {node}\")\n",
    "        for edge in self.adj[node]:\n",
    "            if edge[0] == prev: # 不能直接回到上一个节点，ban这一条边就行\n",
    "                continue\n",
    "            subres = self.dfs(edge, node)\n",
    "            if subres >= 0:\n",
    "                # print(f\"abort out {node}\")\n",
    "                return subres\n",
    "        # print(f\"out {node}\")\n",
    "        self.been[node] = False\n",
    "        self.state.pop()   \n",
    "        return -1\n",
    "        \n",
    "                \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = (len(edges)+1)\n",
    "        degrees = [0] * n\n",
    "        adj_links = {}\n",
    "        n = len(edges)\n",
    "        for i in range(len(edges)):\n",
    "            a, b = edges[i][0], edges[i][1]\n",
    "            if adj_links.get(a) is None:\n",
    "                adj_links[a] = {}\n",
    "            if adj_links.get(b) is None:\n",
    "                adj_links[b] = {}\n",
    "            adj_links[a][b] = i\n",
    "            adj_links[b][a] = i\n",
    "            degrees[a] += 1\n",
    "            degrees[b] += 1\n",
    "        while True:\n",
    "            wait_delete = []\n",
    "            for i in range(1, n+1):\n",
    "                if degrees[i]is not None and degrees[i] < 2:\n",
    "                    wait_delete.append(i)\n",
    "            for node in wait_delete:\n",
    "                adjs = adj_links.get(node)\n",
    "                if adjs is not None:\n",
    "                    for adj in adjs:\n",
    "                        if degrees[adj] is not None:\n",
    "                            degrees[adj] -= 1\n",
    "                degrees[node] = None\n",
    "                adj_links[node] = None\n",
    "            if len(wait_delete) == 0:\n",
    "                break\n",
    "        print(adj_links)\n",
    "        pos = -1\n",
    "        for node in adj_links:\n",
    "            adjs = adj_links.get(node)\n",
    "            if adjs is not None:\n",
    "                for adj in adjs:\n",
    "                    if adj_links.get(adj) is not None:\n",
    "                        pos = max(pos, adjs[adj])\n",
    "        return edges[pos]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        self.graph = collections.defaultdict(list)\n",
    "        self.visited = set()\n",
    "        \n",
    "        for edge in edges:\n",
    "            l = edge[0]\n",
    "            r = edge[1]\n",
    "            if l in  self.graph and r in self.graph:\n",
    "                self.visited.clear()\n",
    "                if self.dfs(l,r):\n",
    "                    return edge\n",
    "            \n",
    "            self.addEdge(r,l)\n",
    "            self.addEdge(l,r)\n",
    "        return None\n",
    "    def addEdge(self,u: int, v: int):\n",
    "            self.graph[u].append(v)\n",
    "            return\n",
    "    def dfs(self,source: int, target: int):\n",
    "        if source == target:\n",
    "            return True\n",
    "        self.visited.add(source)\n",
    "        for item in self.graph[source]:\n",
    "            if item not in self.visited:\n",
    "                if(self.dfs(item,target)):\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        self.parents = [i for i in range(len(edges)+1)]\n",
    "\n",
    "        def find(x):\n",
    "            if x!=self.parents[x]:\n",
    "                x = find(self.parents[x])\n",
    "            return self.parents[x]\n",
    "\n",
    "        for x,y in edges:\n",
    "            print(self.parents,x,y,find(x),find(y))\n",
    "            if find(x)!=find(y):\n",
    "                self.parents[find(x)] = find(y)\n",
    "            else:\n",
    "                return [x,y]\n",
    "        \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 树就是n个点n-1条边；只要我们遍历时发现有环，那就是我们可以删去的边。\n",
    "    #　因为只有一条冗余连接，所以只形成一个环，那么遍历时就能得到。\n",
    "    # 所以问题转化成：找到图中唯一的一个环并记录。\n",
    "    # 方法1：通过dfs遍历并维护一个state（可用hashset），遇到老朋友的时候就抓住环路即可。\n",
    "    # 缺点是可能递归爆栈。\n",
    "    # 方法2：bfs迭代遍历，每一个dfs节点上维护一个上家，并储存(prev, this)（建立一个新图），并同样维护一个state。当老朋友找到时，通过从新图回溯到老朋友到来获得。\n",
    "    # 缺点是有点麻烦。\n",
    "    # 方法3：通过迭代实现dfs。还不错\n",
    "    # 最后说实话 感觉还是直接dfs，不怕爆栈\n",
    "\n",
    "    # 让我们直接dfs。\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        # 首先把【边表】 变成【邻接表】。\n",
    "        self.n = len(edges)\n",
    "        self.adj = [[] for _ in range(self.n)]\n",
    "        self.been = [False] * self.n # 表示在不在\n",
    "        \n",
    "        \n",
    "        for i in range(self.n):\n",
    "            edge = edges[i]\n",
    "            self.adj[edge[0] - 1].append((edge[1] - 1, i)) # 邻接表中也保存边的序号\n",
    "            self.adj[edge[1] - 1].append((edge[0] - 1, i))\n",
    "        # iterative dfs\n",
    "\n",
    "        self.state = [(0, -1)] # 第一个点不带边号\n",
    "        self.been[0] = True\n",
    "        # print(\"Root: in 0\")\n",
    "        for edge in self.adj[0]:\n",
    "            subres = self.dfs(edge, 0)\n",
    "            if subres >= 0:\n",
    "                # print(\"Root: abort out 0\")\n",
    "                return edges[subres]\n",
    "        # print(\"Root: out 0\")\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "    def dfs(self, tup, prev): # node是节点，idx是边的序号\n",
    "        node, idx = tup\n",
    "        # print(f\"dfs node {node} with edge idx {idx}\")\n",
    "        if self.been[node]: # 如果成环\n",
    "            maxidx = idx\n",
    "            start = -1\n",
    "            for i in range(len(self.state)):\n",
    "                if self.state[i][0] == node: # 找到起始idx\n",
    "                    start = i\n",
    "                    break\n",
    "            for i in range(start + 1, len(self.state)): # 找到最大的idx\n",
    "                curidx = self.state[i][1]\n",
    "                if curidx > maxidx:\n",
    "                    maxidx = curidx\n",
    "            return maxidx\n",
    "\n",
    "        self.state.append((node, idx))\n",
    "        self.been[node] = True\n",
    "        # print(f\"in {node}\")\n",
    "        for edge in self.adj[node]:\n",
    "            if edge[0] == prev: # 不能直接回到上一个节点，ban这一条边就行\n",
    "                continue\n",
    "            subres = self.dfs(edge, node)\n",
    "            if subres >= 0:\n",
    "                # print(f\"abort out {node}\")\n",
    "                return subres\n",
    "        # print(f\"out {node}\")\n",
    "        self.been[node] = False\n",
    "        self.state.pop()   \n",
    "        return -1\n",
    "        \n",
    "                \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def IsConnected(self, point_num, points_list, point_dict):\n",
    "        # print(points_list)\n",
    "        # 递归出口\n",
    "        if points_list[point_num - 1] == 1:\n",
    "            return\n",
    "\n",
    "        # 递归操作\n",
    "        points_list[point_num - 1] = 1\n",
    "        for point in point_dict[point_num]:\n",
    "            self.IsConnected(point, points_list, point_dict)\n",
    "    \n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        point_dict = {}\n",
    "        for line in edges:\n",
    "            if line[0] in point_dict:\n",
    "                point_dict[line[0]].append(line[1])\n",
    "            else:\n",
    "                point_dict[line[0]] = [line[1]]\n",
    "            if line[1] in point_dict:\n",
    "                point_dict[line[1]].append(line[0])\n",
    "            else:\n",
    "                point_dict[line[1]] = [line[0]]\n",
    "        \n",
    "        for line in list(reversed(edges)):\n",
    "            points_list = [0] * n\n",
    "            point_dict[line[0]].pop(point_dict[line[0]].index(line[1]))\n",
    "            point_dict[line[1]].pop(point_dict[line[1]].index(line[0]))\n",
    "\n",
    "            # print(line[0], points_list)\n",
    "            # 递归看是否连通\n",
    "            self.IsConnected(line[0], points_list, point_dict)\n",
    "            # print(line[0], points_list)\n",
    "            if 0 not in points_list:\n",
    "                return line\n",
    "            \n",
    "            point_dict[line[0]].append(line[1])\n",
    "            point_dict[line[1]].append(line[0])\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        size=len(edges) #有一个环时 点数=边数\n",
    "        father=[i for i in range(size+1)]\n",
    "        def find(x):\n",
    "            while father[x]!=x:\n",
    "                x=father[x]\n",
    "            return x\n",
    "        \n",
    "        def join(x,y):\n",
    "            r1=find(x)\n",
    "            r2=find(y)\n",
    "            print(x,y,father)\n",
    "            if r1==r2:\n",
    "                return True\n",
    "            else:\n",
    "                father[r2]=r1\n",
    "                return False\n",
    "        print(father)\n",
    "        for s,e in edges:\n",
    "            if join(s,e):\n",
    "                return [s,e]\n",
    "         \n",
    "          \n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        for i in range(n-1, -1, -1):\n",
    "\n",
    "            g = defaultdict(list)\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                x, y = edges[j]\n",
    "                g[x].append(y)\n",
    "                g[y].append(x)\n",
    "                \n",
    "            visited = [True] + [False for _ in range(n)]\n",
    "            def dfs(x):\n",
    "                visited[x] = True\n",
    "                for y in g[x]:\n",
    "                    if not visited[y]:\n",
    "                        dfs(y)\n",
    "            dfs(1)\n",
    "            \n",
    "            if all(visited):\n",
    "                return edges[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        def find(x):\n",
    "            if ref[x]==x:\n",
    "                return x\n",
    "            ref[x]=find(ref[x])\n",
    "            return ref[x]\n",
    "        def merge(x,y):\n",
    "            ref[find(y)]=find(x)\n",
    "            return\n",
    "        n=0\n",
    "        for a,b in edges:\n",
    "            n=max(n,max(a,b))\n",
    "        \n",
    "        ref = [i for i in range(n+1)]\n",
    "        print(ref)\n",
    "        for s,e in edges:\n",
    "            if ref[s]==ref[e]:\n",
    "                return [s,e]\n",
    "            merge(s, e)\n",
    "            for i in range(1,n+1):\n",
    "                ref[i]=find(i)\n",
    "        \n",
    "            print(ref)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        parents = [i for i in range(len(edges))]\n",
    "        def find_root(n):\n",
    "            while parents[n] != n:\n",
    "                   n = parents[n]\n",
    "            return n \n",
    "\n",
    "        def union(n1,n2):\n",
    "            r1 = find_root(n1)\n",
    "            r2 = find_root(n2)\n",
    "            if r1 < r2:\n",
    "               parents[r2] = r1\n",
    "            else:\n",
    "               parents[r1] = r2\n",
    "\n",
    "        def is_connected(n1,n2):\n",
    "            r1 = find_root(n1)\n",
    "            r2 = find_root(n2)\n",
    "            if r1 == r2:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        for pair in edges:\n",
    "            print(parents)\n",
    "            if not is_connected(pair[0]-1,pair[1]-1):\n",
    "                union(pair[0]-1,pair[1]-1)\n",
    "            else:\n",
    "                return pair\n",
    "        \n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n+1))\n",
    "        def find(index):\n",
    "            if parent[index] != index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "\n",
    "        def union(index1,index2):\n",
    "            parent[find(index1)] = find(index2)\n",
    "            print(parent)\n",
    "\n",
    "        for node1, node2 in edges:\n",
    "            if find(node1) != find(node2):\n",
    "                union(node1, node2)\n",
    "            else:\n",
    "                return [node1, node2]\n",
    "        \n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        dic = defaultdict(set)\n",
    "        for f,t in edges:\n",
    "            dic[f].add(t)\n",
    "            dic[t].add(f)\n",
    "        def bfs(start,end):\n",
    "            queue = deque([[start,{start}]])\n",
    "            while queue:\n",
    "                key,visited = queue.popleft()\n",
    "                for u in dic[key]:\n",
    "                    if u not in visited:\n",
    "                        if u == end:\n",
    "                            return True\n",
    "                        visited.add(u)\n",
    "                        new_visited = visited.copy()\n",
    "                        queue.append([u,new_visited])\n",
    "                        visited.remove(u)\n",
    "            return False\n",
    "        for i in range(len(edges)-1,-1,-1):\n",
    "            f,t = edges[i]\n",
    "            dic[f].remove(t)\n",
    "            dic[t].remove(f)\n",
    "            if bfs(f,t):\n",
    "                return [f,t]\n",
    "            dic[f].add(t)\n",
    "            dic[t].add(f)\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        # 初始化\n",
    "        father = list(range(1001))\n",
    "\n",
    "        # 查询\n",
    "        def find(u):\n",
    "            if u == father[u]:\n",
    "                pass\n",
    "            else:\n",
    "                father[u] = find(father[u]) # 路径压缩\n",
    "            return father[u]\n",
    "\n",
    "        # 合并\n",
    "        def join(u, v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            if u == v: # 该if语句可以省略\n",
    "                return \n",
    "            father[u] = v\n",
    "        \n",
    "        # 判断\n",
    "        def is_same(u, v):\n",
    "            return find(u) == find(v)\n",
    "        \n",
    "        # 使用并查集求解\n",
    "        for x in edges:\n",
    "            if is_same(x[0], x[1]):\n",
    "                return x\n",
    "            else:\n",
    "                join(x[0], x[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = 1005\n",
    "        father = [0] * n\n",
    "\n",
    "        def init():\n",
    "            for i in range(n):\n",
    "                father[i] = i\n",
    "        \n",
    "        def find(u):\n",
    "            if u == father[u]:\n",
    "                return u\n",
    "            father[u] = find(father[u])\n",
    "            return father[u]\n",
    "        \n",
    "        def isSame(u, v):\n",
    "            return find(u) == find(v)\n",
    "        \n",
    "        def join(u, v):\n",
    "            u, v = find(u), find(v)\n",
    "            if u == v: return\n",
    "            father[v] = u\n",
    "        \n",
    "        init()\n",
    "        for u, v in edges:\n",
    "            if isSame(u, v):\n",
    "                return [u, v]\n",
    "            join(u, v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        for target_edge in reversed(edges):\n",
    "            dic = defaultdict(list)\n",
    "            visited = [False] * (n+1)\n",
    "            \n",
    "            for edge in edges:\n",
    "                if edge == target_edge:\n",
    "                    continue\n",
    "                dic[edge[0]].append(edge[1])\n",
    "                dic[edge[1]].append(edge[0])\n",
    "            \n",
    "            def dfs(node):\n",
    "                if not visited[node]:\n",
    "                    visited[node] = True\n",
    "                    for adj in dic[node]:\n",
    "                        dfs(adj)\n",
    "            \n",
    "            dfs(target_edge[0])\n",
    "            if visited[target_edge[1]]:\n",
    "                return target_edge"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        parent=list(range(1001))\n",
    "\n",
    "        def find(value):\n",
    "            if parent[value]!=value:\n",
    "                parent[value]=find(parent[value])\n",
    "            return parent[value]\n",
    "        \n",
    "        for t1,t2 in edges:\n",
    "            if find(t1)!=find(t2):\n",
    "                parent[find(t1)]=find(t2)\n",
    "            else:\n",
    "                return [t1,t2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        p = list(range(1005))\n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        def join(u, v):\n",
    "            p[find(v)] = find(u)\n",
    "        def issame(uu, vv):\n",
    "            return find(uu) == find(vv)\n",
    "        for i in range(len(edges)):\n",
    "            if issame(edges[i][0], edges[i][1]):\n",
    "                return edges[i]\n",
    "            else:\n",
    "                join(edges[i][0], edges[i][1])\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        def check(i):\n",
    "            fa = [ i for i in range(n) ]\n",
    "            def find(x):\n",
    "                if x != fa[x]:\n",
    "                    fa[x] = find(fa[x])\n",
    "                return fa[x]\n",
    "            def union(x, y):\n",
    "                fa[find(x)] = find(y)\n",
    "            for j, (x, y) in enumerate(edges):\n",
    "                if j != i:\n",
    "                    union(x-1, y-1)\n",
    "            return sum([ 1 for i in range(n) if fa[i] == i ] ) == 1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if check(i):\n",
    "                return edges[i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        fs = list(range(1005))\n",
    "\n",
    "        def find_fa(x):\n",
    "            if fs[x] != x:            \n",
    "                fs[x] = find_fa(fs[x])\n",
    "            return fs[x]\n",
    "        \n",
    "        def union(x, y):\n",
    "            x, y = find_fa(x), find_fa(y)\n",
    "            if x == y:\n",
    "                return False\n",
    "            \n",
    "            fs[x] = y\n",
    "            return True\n",
    "        \n",
    "        for u, v in edges:\n",
    "            if not union(u, v):\n",
    "                return [u, v]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "思路：并查集-从前往后遍历边，判断边对应的两个节点是否是来自同一个集合，如果不是将两个节点放到同一个集合，如果是返回这条边\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        father = list(range(1001))\n",
    "\n",
    "        def find(x):\n",
    "            if x == father[x]:\n",
    "                return x\n",
    "            else:\n",
    "                father[x] = find(father[x])\n",
    "            return father[x]\n",
    "        \n",
    "        def is_same(u, v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            if u == v:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        def join(u, v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            if u == v:\n",
    "                return\n",
    "            father[v] = u\n",
    "        \n",
    "        for u, v in edges:\n",
    "            if is_same(u, v):\n",
    "                return [u, v]\n",
    "            join(u, v)\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        father = [i for i in range(1005)]\n",
    "        def find(u):\n",
    "            if u == father[u]:\n",
    "                return u\n",
    "            else:\n",
    "                # father[u] = find(father[u])\n",
    "                # return father[u]\n",
    "                return find(father[u])\n",
    "        def join(u,v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            if u == v:\n",
    "                return\n",
    "            else:\n",
    "                father[v] = u\n",
    "        \n",
    "        def issame(u,v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            return u == v\n",
    "        \n",
    "        for i in range(len(edges)):\n",
    "            u = edges[i][0]\n",
    "            v = edges[i][1]\n",
    "            if issame(u,v):\n",
    "                return edges[i]\n",
    "            else:\n",
    "                join(u,v)\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        father = [i for i in range(1002)]\n",
    "        def find(u):\n",
    "            if u == father[u]:\n",
    "                return u\n",
    "            else:\n",
    "                return find(father[u])\n",
    "        result = []\n",
    "        for i,j in edges:\n",
    "            u = find(i)\n",
    "            v = find(j)\n",
    "            if u == v:\n",
    "                result = [i,j]\n",
    "            else:\n",
    "                father[u] = v\n",
    "        return result\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = 1005\n",
    "        fa = [0] * n\n",
    "        for i in range(n):\n",
    "            fa[i] = i\n",
    "\n",
    "        def find(i):\n",
    "            if fa[i] == i:\n",
    "                return i\n",
    "            else:\n",
    "                fa[i] = find(fa[i])\n",
    "                return fa[i]\n",
    "            \n",
    "        def union(i, j):\n",
    "            fi = find(i)\n",
    "            fj = find(j)\n",
    "            fa[fj] = fi\n",
    "\n",
    "        for edge in edges:\n",
    "            if find(edge[0]) != find(edge[1]):\n",
    "                union(edge[0], edge[1])\n",
    "            elif find(edge[0]) == find(edge[1]):\n",
    "                result = edge\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        # 由于节点数量<=1000，fa的长度选取1000\n",
    "        fa = [0] * 1001\n",
    "\n",
    "        # 并查集初始化\n",
    "        def init():\n",
    "            for i in range(1001):\n",
    "                fa[i] = i\n",
    "        \n",
    "        # 并查集里寻根的过程\n",
    "        def find(x):\n",
    "            if x == fa[x]:\n",
    "                return x\n",
    "            else:\n",
    "                fa[x] = find(fa[x])\n",
    "                return fa[x]\n",
    "        \n",
    "        # 判断x, y是否找到同一个根\n",
    "        def isSame(x, y):\n",
    "            # 寻找x, y的根\n",
    "            x, y = find(x), find(y)\n",
    "            return x == y\n",
    "        \n",
    "        # 将y->x 这条边加入并查集\n",
    "        def merge(x, y):\n",
    "            # 寻找x, y的根\n",
    "            x, y = find(x), find(y)\n",
    "            # 如果根相同，说明在同一个集合，不用两个节点相连直接返回\n",
    "            if x == y: return\n",
    "            fa[y] = x\n",
    "        \n",
    "        res = []\n",
    "        init()\n",
    "        for edge in edges:\n",
    "            if isSame(edge[0], edge[1]):\n",
    "                res = edge\n",
    "            else:\n",
    "                merge(edge[0], edge[1])\n",
    "\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        father = [i for i in range(1005)]\n",
    "        def find(u):\n",
    "            if u != father[u]:\n",
    "                father[u] = find(father[u])\n",
    "            return father[u]\n",
    "        def join(u, v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            if u == v:\n",
    "                return\n",
    "            father[v] = u\n",
    "        def same(u, v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            return v == u\n",
    "        result = []\n",
    "        for e in edges:\n",
    "            if same(e[0], e[1]):\n",
    "                result = e\n",
    "            else:\n",
    "                join(e[0], e[1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = 1005\n",
    "        father = [i for i in range(n)]\n",
    "        def find(u):\n",
    "            if u == father[u]:\n",
    "                return u\n",
    "            else:\n",
    "                father[u] = find(father[u])\n",
    "                return father[u]\n",
    "        def isame(u,v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            return u==v\n",
    "        def join(u,v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            if u==v:\n",
    "                return\n",
    "            else:\n",
    "                father[v] = u\n",
    "        for i in range(len(edges)):\n",
    "            if isame(edges[i][0],edges[i][1]):\n",
    "                return edges[i]\n",
    "            else:\n",
    "                join(edges[i][0],edges[i][1])\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        # 初始化\n",
    "        father = list(range(1001))\n",
    "\n",
    "        # 查询\n",
    "        def find(u):\n",
    "            if u == father[u]:\n",
    "                return u\n",
    "            else:\n",
    "                father[u] = find(father[u]) # 路径压缩\n",
    "                return father[u]\n",
    "\n",
    "        # 合并\n",
    "        def join(u, v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            if u == v: # 该if语句可以省略\n",
    "                return \n",
    "            father[v] = u\n",
    "        \n",
    "        # 判断\n",
    "        def is_same(u, v):\n",
    "            return find(u) == find(v)\n",
    "        \n",
    "        # 使用并查集求解\n",
    "        for x in edges:\n",
    "            if is_same(x[0], x[1]):\n",
    "                return x\n",
    "            else:\n",
    "                join(x[0], x[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        graph = {}\n",
    "        for a, b in edges:\n",
    "            graph[a] = graph.get(a, []) + [b]\n",
    "            graph[b] = graph.get(b, []) + [a]\n",
    "        \n",
    "        def dfs(path, node):\n",
    "            # print(f'{path}, {node}')\n",
    "            nonlocal cycle\n",
    "            if node in path: # found cycle\n",
    "                cycle = path[path.index(node):]\n",
    "                # cycle = path\n",
    "                return\n",
    "            if node not in graph:\n",
    "                return\n",
    "            for next_node in graph[node]:\n",
    "                if path and next_node == path[-1]: # no backwards\n",
    "                    continue\n",
    "                dfs(path+[node], next_node)\n",
    "                if cycle:\n",
    "                    break\n",
    "        \n",
    "        cycle = []\n",
    "        dfs([], 1)\n",
    "        cycle1 = set([(cycle[i], cycle[i+1]) for i in range(len(cycle)-1)])\n",
    "        cycle1.add((cycle[0], cycle[-1]))\n",
    "\n",
    "        # print(cycle)\n",
    "        # print(cycle1)\n",
    "\n",
    "        for i in range(len(edges)-1, -1, -1):\n",
    "            a, b = edges[i]\n",
    "            if (a, b) in cycle1 or (b, a) in cycle1:\n",
    "                return [a, b]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n=1005\n",
    "        fa=[i for i in range(n)]\n",
    "        for i in range(n):\n",
    "            fa[i]=i\n",
    "        def find(u):\n",
    "            if u!=fa[u]:\n",
    "                fa[u]=find(fa[u])\n",
    "            return fa[u]\n",
    "        def join(u,v):\n",
    "            u=find(u)\n",
    "            v=find(v)\n",
    "            if u!=v:\n",
    "                fa[u]=v\n",
    "        for i,j in edges:\n",
    "            if find(i)==find(j):\n",
    "                return (i,j)\n",
    "            else:\n",
    "                join(i,j)\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        graph = collections.defaultdict(list)\n",
    "\n",
    "        visited = collections.defaultdict(int)\n",
    "\n",
    "        def dfs(i,j):\n",
    "            visited[i]=1\n",
    "            if i==j:\n",
    "                return True\n",
    "            for adj_node in graph[i]:\n",
    "                if not visited[adj_node]:\n",
    "                    if dfs(adj_node,j):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        for edge in edges:\n",
    "            if edge[0] in graph.keys() and edge[1] in graph.keys():\n",
    "                visited = collections.defaultdict(int)\n",
    "                if dfs(edge[0],edge[1]):\n",
    "                    return edge\n",
    "            \n",
    "            #遍历到图中不存在的点，加到图中\n",
    "            graph[edge[0]].append(edge[1])\n",
    "            graph[edge[1]].append(edge[0])\n",
    "\n",
    "        return null"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        father=[ i for i in range(1001)]\n",
    "        def find(u):\n",
    "            if father[u] == u:\n",
    "                return u\n",
    "            father[u] = find(father[u])\n",
    "            return father[u]\n",
    "        def issame(u,v):\n",
    "            return find(u) == find(v)\n",
    "        def union(u,v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            if u == v:\n",
    "                return\n",
    "            father[v] = u\n",
    "\n",
    "        for i,j in edges:\n",
    "            if not issame(i,j):\n",
    "                union(i,j)\n",
    "            else:\n",
    "                return (i,j)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        dt=dict()\n",
    "        def dfs(x,y):\n",
    "            if x not in dt:\n",
    "                return False\n",
    "            nex=dt[x]\n",
    "            if y in nex:\n",
    "                return True\n",
    "            for p in nex:\n",
    "                if p in visited:\n",
    "                    continue\n",
    "                visited.add(p)\n",
    "                if dfs(p,y):\n",
    "                    return True\n",
    "                visited.remove(p)\n",
    "            return False\n",
    "        for x,y in edges:\n",
    "            visited=set()\n",
    "            if dfs(x,y):\n",
    "                return [x,y]\n",
    "            if x in dt:\n",
    "                dt[x].append(y)\n",
    "            else:\n",
    "                dt[x]=[y]\n",
    "            if y in dt:\n",
    "                dt[y].append(x)\n",
    "            else:\n",
    "                dt[y]=[x]\n",
    "        \n",
    "       \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        parent = [i for i in range(1001)]\n",
    "        def find(x: int) -> int:\n",
    "            if x != parent[x]:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "        \n",
    "        for e in edges:\n",
    "            p0, p1 = find(e[0]), find(e[1])\n",
    "\n",
    "            if p0 != p1:\n",
    "                parent[p1] = parent[p0]\n",
    "            else:\n",
    "                return e\n",
    "        \n",
    "        return []\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
